package seqlist.带头单链表;

/**
 * 带头（虚拟头）单链表
 */

public class Head_Linked_list {
    private int size;//有效节点的个数，不包含虚拟头节点
    //创建一个虚拟头节点
    // 实实在在存在的Node对象，不存储数据，就作为火车头
    private Node dummyHead = new Node();

    //头插--精简写法
    public void addFirst(int val){

        dummyHead.next = new Node(val, dummyHead.next);
        size ++;

        //第二种，简化后的
        /*
        Node newNode = new Node(val, dummyHead.next);//创建出一个新节点
        dummyHead.next = newNode;
        size++;
         */

        //第一种写法
        /*
        Node newNode = new Node();//创建出一个新节点
        newNode.val = val;//赋值

        newNode.next = dummyHead.next;
        dummyHead.next = newNode;
        size ++;//有效元素 + 1

         */
    }

    /**
     *在 index 索引处插入节点
     */
    public void add(int index, int val){
        //对索引判断
        if(index < 0 || index > size){
            System.out.println("插入的索引错误！");
            return;
        }
        Node prve = dummyHead;//始终充当前驱的身份
        //想要让prve成为要插入位置的前驱，就需要知道要走几步
        //作图得知，插入index位置，需要做 index步
        for (int i = 0; i < index; i++) {
            prve = prve.next;
        }//循环后，prve就是前驱的位置了

        //方法1
        //让新节点指向 前驱的 后面的后面一个
//        Node node = new Node(val);//要插入的对象
//        node.next = prve.next;
//        prve.next = node;//前驱指向新节点
//        size++;

        //方法2 简便写法，跟之前都一样
        //让新节点指向 前驱的 后面的后面一个
        prve.next = new Node(val, prve.next);//要插入的对象
        size++;
    }

    //尾插
    public void addLast(int val){
        add(size, val);
    }

    /**
     * 查询第一个为val值的节点，返回索引
     * 不存在则返回 -1
     */
     public int getByValue(int val){
         Node prve = dummyHead.next;
         for (int i = 0; prve != null ; i++) {

             if(prve.val == val){
                 return i;
             }
             prve = prve.next;
         }

         //如果都没找到，则不存在 返回 -1
         return -1;
     }

    /**
     *查询给的索引值是否合理
     */
    private boolean rangeCheck(int index) {
        if(index < 0 || index >= size){
            return false;
        }
        return true;
    }


    /**
     * 查询 index 索引处的节点值
     */
     public int get(int index){
         if(rangeCheck(index)){
             //走 index + 1步
             Node node = dummyHead;
             for (int i = 0; i < index + 1; i++) {
                 node = node.next;
             }
             return node.val;
         }
         System.out.println("查询的索引值有误");
         return -1;
     }

    /**
     * 查询链表中是否包含val值
     */
     public boolean contain(int val){
         return getByValue(val) != -1;
     }

    /**
     * 修改 index 索引处的节点值
     * 并返回修改前的值
     */
     public int set(int index, int val){
         if(rangeCheck(index)){
             Node cur = Index(index);
             int rep = cur.val;
             cur.val = val;
             return rep;
         }
         System.out.println("输入的修改索引错误");
         return -1;
     }

    /**
     * 输入索引值，给你返回该节点的地址
     */
     private Node Index(int index){
         //这里有个特殊情况，当index为 -1，默认代表给它虚拟头节点的地址
         if(rangeCheck(index) || index == -1){
             //需要走 index + 1步
             Node node = dummyHead;
             for (int i = 0; i < index + 1; i++) {
                  node = node.next;
             }
             return node;
         }
         return null;
     }

    /**
     * 删除 index 索引处的节点，并返回原来的值
     * @return
     */
     public int remove(int index){
         if(rangeCheck(index)){
             //找到删除节点的前驱
             Node prve = Index(index - 1);//前驱
             Node node = prve.next;//带删除的节点
             prve.next = node.next;//删除跳过
             node.next = null;//断开连接
             size --;
             return node.val;
         }
         System.out.println("输入的删除索引错误");
         return -1;
     }


    //头删
    public int removeFirst(){
         return remove(0);
    }
    //尾删
    public int removeLast(){
        return remove(size - 1);
    }

    /**
     * 删除第一个值为 val的节点，并返回改节点值
     * @return
     */
     public int removeValueOnce(int val){

         //普通的写法
//         for (Node prve = dummyHead; prve.next != null ; prve = prve.next) {
//
//             if(prve.next.val == val){
//                 Node node = prve.next;//待删除的节点
//                 prve.next = node.next;//跳过待删除的节点
//                 node.next = null;//断开
//                 size--;
//                 return node.val;
//             }
//
//         }
//
//         //说明没有val值删除
//         return -1;

         //运用方法来写
         int index = getByValue(val);//返回第一个为val节点的索引
         return remove(index);
     }

    /**
     * 删除全部为val值的节点
     * @return
     */
     public void removeAllValue(int val){
         //用双指针的思路
         Node prve = dummyHead;//前驱

         while(prve.next != null){
             Node node = prve.next;//前驱的后一个节点，用来判断是否是删除节点
             if(node.val == val){
                 prve.next = node.next;//跳过待删除节点
                 node.next = null;//断开
                 size--;
             }else{
                 //只有确保下一个节点不是删除节点，才能移动prve
                 prve = prve.next;
             }
         }

     }


    //完善toString方法
    public String toString(){
        String rep = "";
        for (Node x = dummyHead.next; x != null ; x = x.next) {
             rep += x.val;
             rep += " -> ";
        }
        rep += "NULL";
        return rep;
    }

}


/**
 * 单链表的每个节点-车厢类
 */
class Node {

    int val;
    Node next;

    //无参构造
    public Node() {
    }

    //构造方法
    public Node(int val) {
        this.val = val;
    }

    //构造方法
    public Node(int val, Node next) {
        this.val = val;
        this.next = next;
    }
}
